package com.leetcode.No1793;

import org.junit.Test;

import java.util.*;

public class Solution2 {
    public int maximumScore(int[] nums, int k) {
        Map<Integer, Integer> leftMaxYX = new TreeMap<>((m1, m2) -> m2 - m1);
        Map<Integer, Integer> rightMaxYX = new TreeMap<>((m1, m2) -> m2 - m1);

        int maxY = nums[k];
        for (int i = k; i >= 0; --i) {
            maxY = Math.min(maxY, nums[i]);
            leftMaxYX.put(maxY, k - i + 1);
        }
        maxY = nums[k];
        for (int i = k; i < nums.length; ++i) {
            maxY = Math.min(maxY, nums[i]);
            rightMaxYX.put(maxY, i - k + 1);
        }

        HashSet<Integer> set = new HashSet<>();
        set.addAll(leftMaxYX.keySet());
        set.addAll(rightMaxYX.keySet());
        List<Integer> allList = new ArrayList<>(set);
        allList.sort((i1, i2) -> i2 - i1);

        int idx = 0;
        Map<Integer, Integer> tmpLeftMaxXY = new HashMap<>();
        int leftI = 0;
        Integer[] leftMaxYs = leftMaxYX.keySet().toArray(new Integer[0]);
        while (allList.get(idx) > leftMaxYs[leftI]) {
            tmpLeftMaxXY.put(allList.get(idx), 1);
            ++idx;
        }
        while (idx < allList.size()) {
            if (leftI < leftMaxYs.length && allList.get(idx).equals(leftMaxYs[leftI])) {
                ++idx;
                ++leftI;
                continue;
            }
            if (leftI < leftMaxYs.length) {
                while (allList.get(idx) > leftMaxYs[leftI]) {
                    tmpLeftMaxXY.put(allList.get(idx++), leftMaxYX.get(leftMaxYs[leftI - 1]));
                }
            } else {
                while (idx < allList.size()) {
                    tmpLeftMaxXY.put(allList.get(idx++), leftMaxYX.get(leftMaxYs[leftMaxYs.length - 1]));
                }
            }
        }
        leftMaxYX.putAll(tmpLeftMaxXY);

        Map<Integer, Integer> tmpRightMaxXY = new HashMap<>();
        idx = 0;
        int rightI = 0;
        Integer[] rightMaxYs = rightMaxYX.keySet().toArray(new Integer[0]);
        while (allList.get(idx) > rightMaxYs[rightI]) {
            tmpRightMaxXY.put(allList.get(idx), 1);
            ++idx;
        }
        while (idx < allList.size()) {
            if (rightI < rightMaxYs.length && allList.get(idx).equals(rightMaxYs[rightI])) {
                ++idx;
                ++rightI;
                continue;
            }
            if (rightI < rightMaxYs.length) {
                while (allList.get(idx) > rightMaxYs[rightI]) {
                    tmpRightMaxXY.put(allList.get(idx++), rightMaxYX.get(rightMaxYs[rightI - 1]));
                }
            } else {
                while (idx < allList.size()) {
                    tmpRightMaxXY.put(allList.get(idx++), rightMaxYX.get(rightMaxYs[rightMaxYs.length - 1]));
                }
            }
        }
        rightMaxYX.putAll(tmpRightMaxXY);

        int result = 0;
        for (Integer m : allList) {
            int left = (leftMaxYX.get(m) == null) ? 0 : leftMaxYX.get(m);
            int right = (rightMaxYX.get(m) == null) ? 0 : rightMaxYX.get(m);
            result = Math.max(result, (left + right - 1) * m);
        }
        return result;
    }

    @Test
    public void test() {
//        int[] nums = new int[]{1,4,3,7,4,5};
        int[] nums = new int[]{5,5,4,5,4,1,1,1};
        int k = 0;
        System.out.println(maximumScore(nums, k));
    }
}
